import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;


public class Graphe {

	/** V est l'ensemble des sommets de ce graphe. */
	ArrayList<Sommet> V = new ArrayList<Sommet>();
	/** E est l'ensemble des arêtes de ce graphe. */
	ArrayList<Arete> E = new ArrayList<Arete>();
	/** listcomposante est l'ensemble des composantes connexes du graphe. */
	ArrayList<ArrayList<Sommet> > listcomposante = new ArrayList<ArrayList<Sommet> >();
	/** composanteConnexe est la plus grande composante connexe du graphe. */
	Graphe composanteConnexe;
	/** date permet de gérer les marquages. */
	int date ;
	/** isConnexe est l'attribut utilisé pour savoir si un graphe est connexe ou non. */
	boolean isConnexe ;

	/**
	 * Constructeur par défaut.
	 */
	public Graphe() {
		super();
	}

	/**
	 * Constructeur de graphe complet.
	 * @param sommets la liste de sommets du graphe.
	 * @param aretes la liste d'arêtes du graphe.
	 */
	public Graphe(ArrayList<Sommet> sommets, ArrayList<Arete> aretes) {
		super();
		this.V = sommets;
		this.E = aretes;
	}

	/**
	 * Constructeur de graphe par lecture de fichier.
	 * @param chemin le chemin (path) du fichier sur le disque.
	 */
	public Graphe(String chemin) {
		super();
		lireFichier(chemin);
	}

	//construire un graphe aléatoire
	/**
	 * Constructeur aléatoire de graphe.
	 * 
	 * @param nbSommets le nombre de sommets souhaités dans ce graphe.
	 * @param proba la probabilité qu'il y ait une arête entre deux sommets distincts.
	 * @param borneInf la valeur minimum possible que peut prendre la valuation d'une arête.
	 * @param borneSup la valeur maximum possible que peut prendre la valuation d'une arête.
	 */
	public Graphe(int nbSommets, float proba, int borneInf, int borneSup) {

		// Initialisation des variables de la classe.
		V = new ArrayList<Sommet>();
		E = new ArrayList<Arete>();

		// Génération des nbSommets sommets voulus.
		for (int i = 0; i < nbSommets; i++) {
			Sommet s = new Sommet(i);
			V.add(s);
		}

		// Génération aléatoire des arêtes.
		// On parcours chaque sommet de V (parcours A).
		for (int i = 0; i < V.size(); i++) {
			// On compare chaque sommet à tous les autres (parcours B).
			for (int j = 0; j < V.size(); j++){
				//on tire un nombre aléatoire entre 0.1

				if (Math.random()<proba){
					Arete a;
					int sens, valuation ;
					Random random ;

					random = new Random();

					// Valuation de l'arête aléatoire
					valuation = borneInf + random.nextInt(borneSup - borneInf);

					// Orientation aléatoire
					sens = random.nextInt(2);
					if(sens == 1) {
						a = new Arete(V.get(i), V.get(j), valuation);
					}
					else {
						a = new Arete(V.get(j), V.get(i), valuation);
					}
					// Ajout de l'arête à la liste d'arêtes E
					E.add(a);
				}
			} // Fin du parcous B
		} // Fin du parcours A
	}

	//Enregistrer le graphe genérer dans un fichier
	/**
	 * Fonction d'enregistrement dans un fichier.
	 * Le fichier générer se nommera generated_graphe.desc.
	 */
	public void enregistrerFichier() {
		File outputFile = new File("generated_graphe.desc");
		try {
			FileWriter out = new FileWriter(outputFile);

			for(int i = 0 ; i<E.size() ; i++){
				out.write(E.get(i).toString()+"\n");
			}

			out.close();

		} catch (IOException e) {
			e.printStackTrace();
		}

	}

	/**
	 * Getteur de l'attribut V.
	 * @return la valeur de l'attribut V.
	 */
	public ArrayList<Sommet> getV() {
		return V;
	}
	/**
	 * Setteur de l'attribut V.
	 * @param V la nouvelle valeur à affecter à l'attribut V.
	 */
	public void setV(ArrayList<Sommet> v) {
		V = v;
	}
	/**
	 * Getteur de l'attribut E.
	 * @return la valeur de l'attribut E.
	 */
	public ArrayList<Arete> getE() {
		return E;
	}
	/**
	 * Setteur de l'attribut E.
	 * @param E la nouvelle valeur à affecter à l'attribut E.
	 */
	public void setE(ArrayList<Arete> e) {
		E = e;
	}

	/**
	 * Fonction qui permet de récupérer le poids d'un graphe,
	 * c'est-à-dire la somme des valuations de chacune de ses
	 * arêtes.
	 * 
	 * @return le poids total des arêtes.
	 */
	public int getPoids() {
		int somme = 0 ;
		for(Arete a : E) {
			somme += a.getValuation();
		}
		return somme ;
	}

	/**
	 * Fonction qui permet de compter le nombre de sommets présents
	 * de la liste de sommets V.
	 * 
	 * @return le nombre de sommets du graphe.
	 */
	public int getNbSommets() {
		return V.size();
	}

	/**
	 * Fonction qui permet de savoir si un graphe est connexe ou non.
	 * 
	 * @return vrai si le graphe est connexe, faux sinon.
	 */
	public boolean isConnexe() {
		if(isConnexe) return true ;
		else return false ;
	}

	/**
	 * Surcharge de l'opérateur toString.
	 * 
	 * Cette méthode permet la construction du fichier.
	 */
	@Override
	public String toString() {
		String chaine = "";

		for (int i = 0; i < E.size(); i++) {
			chaine = chaine + E.get(i) + "\n";
		}
		return chaine;
	}

	//methode de chargement d'un graphe depuis un fichier
	/**
	 * Fonction qui permet de lire un fichier et d'en extraire le graphe
	 * qu'il contient.
	 * @param chemin le chemin (path) du fichier qu'on va lire.
	 */
	public void lireFichier(String chemin){

		Scanner scanner ;
		String str ;
		String[] mots ;

		scanner = null ;
		str = null ;
		mots = null ;

		try {
			scanner = new Scanner(new FileReader(chemin));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		while (scanner.hasNextLine()){
			Arete tmp ;
			Sommet source, destination ;

			str = scanner.nextLine();
			mots = str.split(" ");

			source = new Sommet(Integer.parseInt(mots[0]));
			destination = new Sommet(Integer.parseInt(mots[1]));
			tmp = new Arete(source, destination, Integer.parseInt(mots[2]));

			// Ajout des arêtes
			// Ajout du sommet source s'il n'est pas déjà dans la liste
			if (!V.contains(source))
			{
				V.add(source);
			}
			// Ajout du sommet destination s'il n'est pas déjà dans la liste
			if (!V.contains(destination))
			{
				V.add(destination);
			}
			// Ajout de l'arête à la liste d'arêtes
			E.add(tmp);
		}
	}

	/**
	 * Procedure renvoyant la plus grande composante connexe d'un graphe, qui est donc
	 * un sous graphe de ce premier graphe.
	 * 
	 * @return la plus grande composante connexe du graphe.
	 */
	public Graphe connexe(){
		//initialisation
		for(Sommet s :V){
			s.setParent(null);
			s.setCouleur("green");
			s.setDecouverte(0);
			s.setFinish(0);
		}
		date = 1;

		for(Sommet s :V){
			if (s.getCouleur().equals("green")){
				ArrayList<Sommet> listsommets = new ArrayList<Sommet>();
				//DFS(V.indexOf(s),listsommets);
				DFS(s,listsommets);
				listcomposante.add(listsommets);
			}
		}
		ArrayList<Arete> listArete;
		if(listcomposante.size()>1) {
			int t=0;
			for(int i=1; i<listcomposante.size();i++){
				if(listcomposante.get(i).size()>listcomposante.get(t).size()){
					t = i;
				}
			}

			listArete = new ArrayList<Arete>();
			for(Arete a : E){
				if(listcomposante.get(t).contains( a.getSource()) && listcomposante.get(t).contains( a.getDestination())){
					listArete.add(a);
				}
			}

			composanteConnexe = new Graphe(listcomposante.get(t), listArete);
			System.out.println("Non connexe");
			isConnexe = false ;
		}
		else{
			listArete = new ArrayList<Arete>();
			for(Arete a : E){
				if(listcomposante.get(0).contains( a.getSource()) && listcomposante.get(0).contains( a.getDestination()))
					listArete.add(a);
			}
			composanteConnexe = new Graphe(listcomposante.get(0), listArete);
			System.out.println("Connexe");
			isConnexe = true ;
		}

		//System.out.println(composanteConnexe);
		return composanteConnexe;

	}


	void DFS(Sommet ind, ArrayList<Sommet> listsommets){

		ind.setCouleur("orange");
		ind.setDecouverte(date);
		date++;
		//ArrayList<Integer> ls = new ArrayList<Integer>();
		//ls = successeur(ind);
		ArrayList<Sommet> ls = new ArrayList<Sommet>();
		ls = voisins(ind);
		if(!listsommets.contains(ind))
			listsommets.add(ind);

		for(Sommet s2 :ls ){
			if(s2.getCouleur().equals("green"))
			{
				s2.setParent(ind);
				DFS(s2,listsommets);
			}
		}
		ind.setCouleur("rouge");
		ind.setFinish(date);
		date++;
	}

	/*void DFS(Sommet ind, ArrayList<Sommet> listsommets){
		V.get(ind).setCouleur("orange");
		V.get(ind).setDecouverte(date);
		date++;
		//ArrayList<Integer> ls = new ArrayList<Integer>();
		//ls = successeur(ind);
		ArrayList<Sommet> ls = new ArrayList<Sommet>();
		ls = voisins(ind);
		listsommets.add(V.get(ind));

		for(Integer s2 :ls ){
			if(V.get(s2).getCouleur().equals("green"))
			{
				V.get(s2).setParent(V.get(ind));
				DFS(s2,listsommets);
			}
		}
		V.get(ind).setCouleur("rouge");
		V.get(ind).setFinish(date);
		date++;
	}*/

	/*
	void DFS(Sommet s){
		Date d = new Date();
		s.setColor("orange");

		// on crée un nouveau graphe
		//		Graphe g = new Graphe();
		//		ArrayList<Sommet> S = new ArrayList<Sommet>();
		//		ArrayList<Arete> A = new ArrayList<Arete>();
		//		S.add(s);
		// a voir

		s.setDecouverte(d.getTime());

		//on met les successeurs de s dans une liste (ls)
		ArrayList<Sommet> ls = new ArrayList<Sommet>();
		ls = successeur(s);

		//pour tous les sommets dans ls (donc pour tous les successeurs de s)
		for(Sommet s2 :ls ){

			String tmp = s2.getColor();
			//pour eviter des null pointeur exception (si s2.getColor == null)
			if(tmp!=null){

				//si le successeur de s est vert
				if(s2.getColor().equals("green"))
				{	
					//alors on met s en tant que parent de ce successeur
					s2.setParent(s);
					//et on rapelle DFS pour ce successeur
					DFS(s2);
				}
			}
		}

		d = new Date();
		s.setColor("rouge");
		s.setFinish(d.getTime());


	}*/

	/*
	//procédure renvoyant dans une arrayList les successeurs d'un sommet passé en paramètre
	ArrayList<Sommet> successeur(Sommet s){

		ArrayList<Sommet> are = new ArrayList<Sommet>();

		//pour toutes les aretes présentes dans l'atribut aretes du graphe
		for(Arete a :aretes){
			//si la source de l'arete est égale au sommet passé en parametre
			if(a.getSource().equals(s)){
				//on ajoute dans are (notre liste de sommets) le sommet de destination
				are.add(a.getDestination());
			}
		}

		return are;
	}*/

	//	ArrayList<Integer> successeur(int s){
	//
	//		ArrayList<Integer> are = new ArrayList<Integer>();
	//		for(int i=0; i<E.size(); i++){
	//			if(E.get(i).getSource().equals(V.get(s))){
	//				for(int j=0; j<V.size(); j++){
	//					if(V.get(j).equals(E.get(i).getDestination())) {
	//						//						System.out.println(j);
	//						are.add(j);
	//						break;
	//					}
	//				}
	//			}
	//		}
	//
	//		return are;
	//	}


	ArrayList<Sommet> voisins(Sommet s){
		ArrayList<Sommet> som = new ArrayList<Sommet>();

		//pour toutes les aretes présentes dans l'atribut aretes du graphe
		for(Arete a :E){
			//si la source de l'arete est égale au sommet passé en parametre
			if((a.getSource().equals(s))&&(!som.contains(a))){
				//on l'ajoute dans are 
				som.add(a.getDestination());
			}
			if((a.getDestination().equals(s))&&(!som.contains(a))){
				som.add(a.getSource());
			}
		}

		return som;
	}


	//procédure renvoyant dans une arrayList les aretes adjacentes au sommet passé en parametre
	// dont le sommet passé en parametre est la source
	ArrayList<Arete> adjacente(Sommet s){

		ArrayList<Arete> are = new ArrayList<Arete>();

		//pour toutes les aretes présentes dans l'atribut aretes du graphe
		for(Arete a : E){
			//si la source de l'arete est égale au sommet passé en parametre
			if((a.getSource().equals(s))||(a.getDestination().equals(s))&&(!are.contains(a))){
				//on l'ajoute dans are 
				are.add(a);
			}
		}

		return are;
	}


	/*Procedure calculant, à l'aide de l'algorithme de Prim, un arbre couvrant de poids minimum
	 * Prend en entrée un graphe 
	 * et renvoie un autre graphe (qui est évidemment un sous graphe du premier) représentant 
	 * l'arbre couvrant de poids minimum
	 */
	Graphe prim(){

		//on commence par créer un graphe -> c'est l'arbre couvrant de poids minimum.
		Graphe prim = new Graphe();
		// ce graphe est composé d'un ensemble d'arete et d'un ensemble de sommets,
		// ce sont eux que l'on va remplir au fur et a mesure
		ArrayList<Sommet> VP = new ArrayList<Sommet>();
		ArrayList<Arete> EP = new ArrayList<Arete>();

		ArrayList<Arete> ls = new ArrayList<Arete>();
		Sommet s ;
		//on met le premier sommet de G dans VP
		VP.add(V.get(0));

		s = V.get(0);
		//tant que l'on n'a pas parcouru tous les sommets  
		while(VP.size()!=V.size()){
			// a = +infini
			double a = Double.POSITIVE_INFINITY;
			Arete ar = new Arete();
			//on parcours tous les sommets présents dans VP (1 seul au premier passage)

			a = Double.POSITIVE_INFINITY;
			//on met les successeurs de s dans une liste (ls)

			ArrayList<Arete> lTemp = adjacente(s);
			for(Arete tmp : lTemp) {
				if(!ls.contains(tmp) && !EP.contains(tmp)) {
					ls.add(tmp); 
				}
			}

			// et pour chaque sommet, on recherche l'arete la plus "legère" (de poids minimal)
			for(Arete arete:ls){
				// tout en faisant attention que l'arete que l'on choisit ne forme pas de cycle

				if((arete.getValuation()<a)&&(!EP.contains(arete)))
				{
					if(VP.contains(arete.getSource())) {
						if(!VP.contains(arete.getDestination())) {
							a=arete.getValuation();
							ar=arete;
						}
					}
					else if(VP.contains(arete.getDestination())) {
						if(!VP.contains(arete.getSource())) {
							a=arete.getValuation();
							ar=arete;
						}
					}
				}
			}
			//on ajoute notre arete dans l'ensemble des aretes du graphe que l'on va renvoyer
			EP.add(ar);
			ls.remove(ar);
			//ainsi que le sommet de destination de cette arete, qui fait maintenant parti des sommets atteints
			if(VP.contains(ar.getSource())) {
				if(!VP.contains(ar.getDestination())) {
					VP.add(ar.getDestination());
					s = ar.getDestination();
				}
			}
			else {
				if(!VP.contains(ar.getSource())) {
					VP.add(ar.getSource());
					s = ar.getSource();
				}
			}
		}
		prim.E=EP;
		prim.V=VP;
		return prim;
	}
}